#include<vector>
#include<deque>
#include<unordered_set>
#include<unordered_map>
using namespace std;

class Solution {
private:
    int findParent(vector<int>& parents, int index) {
        if (parents[index] == -1)
            return index;
        return findParent(parents, parents[index]);
    }
    void unions(vector<int>& parents, int index1, int index2) {
        int p1 = findParent(parents, index1);
        int p2 = findParent(parents, index2);
        if(p1!=p2)
            parents[p2] = p1;
    }

public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        if (n < 2) return n;
        vector<int>parents(n,-1);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j] == 1)
                    unions(parents, i, j);
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (parents[i] == -1)
                ++res;
        }
        return res;
    }
};



//class Solution {
//public:
//    int findCircleNum(vector<vector<int>>& M) {
//        int n = M.size();
//        if (n < 2) return n;
//        unordered_map<int, vector<int>>graph;
//        for (int i = 0; i < n; ++i) {
//            for (int j = i + 1; j < n; ++j) {
//                if (M[i][j] == 1) {
//                    graph[i].push_back(j);
//                    graph[j].push_back(i);
//                }
//            }
//        }
//        deque<int>queue;
//        unordered_set<int>visited;
//        int res = 0;
//        for (int i = 0; i < n; ++i) {
//            if (visited.find(i) != visited.end())
//                continue;
//            queue.push_back(i);
//            ++res;
//            while (!queue.empty()) {
//                int size = queue.size();
//                while (size > 0) {
//                    --size;
//                    int index = queue.front();
//                    queue.pop_front();
//                    for (auto k:graph[index]) {
//                        if (visited.find(k) == visited.end()) {
//                            queue.push_back(k);
//                            visited.insert(k);
//                        }
//                    }
//                }
//            }
//        }
//        return res;
//
//    }
//};